1. Field
This application relates to network elements and, more particularly, to a method for highly efficient heap management.
2. Description of the Related Art
Data communication networks may include various switches, nodes, routers, and other devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network elements”. Data is communicated through the data communication network by passing protocol data units, such as frames, packets, cells, or segments, between the network elements by utilizing one or more communication links. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
Network elements are designed to handle packets of data efficiently to minimize the amount of delay associated with transmission of the data on the network. Conventionally, this is implemented by using hardware in a data plane of the network element to forward packets of data, while using software in a control plane of the network element to configure the network element to cooperate with other network elements on the network. For example, a network element may include a routing process, which runs in the control plane, that enables the network element to have a synchronized view of the network topology so that the network element is able to forward packets of data across the network toward its intended destination. Multiple processes may be running in the control plane to enable the network element to interact with other network elements on the network and forward data packets on the network.
The applications running in the control plane make decisions about how particular types of traffic should be handled by the network element to allow packets of data to be properly forwarded on the network. As these decisions are made, the control plane programs the hardware in the dataplane to enable the dataplane to be adjusted to properly handle traffic as it is received. The data plane includes ASICs, FPGAs, and other hardware elements designed to receive packets of data, perform lookup operations on specified fields of packet headers, and make forwarding decisions as to how the packet should be transmitted on the network. Lookup operations are typically implemented using tables and registers containing entries populated by the control plane.
Both the control plane and the data plane use memory to store tables and other values in connection with implementing forwarding decisions. To manage the memory, a heap manager is required which keeps track of which memory addresses are currently in use and which are available.
A heap is a pre-allocated contiguous chunk of memory that is used by application tables to dynamically allocate and free data within the course of their runtime operations. The heap is divided into basic units of usage, which are referred to herein as “memory cells” or “cells” for short. A cell can be configured to have a size that is 1× or multiple of the size of the underlying physical memory location. For example, assume that the underlying memory has a memory cell size of 4 bytes. Memory would then be allocated to include 4 bytes, 8 bytes, 12 bytes, or another number of contiguous 4 byte cells. Typically, the cell size is selected such that it optimizes and makes efficient use of the underlying physical memory.
The heap labels its constituent cells by a zero-based identifier called a Cell Index. A data structure keeps track of free cells, and is maintained by the heap manager. When an application requires data storage in its course of execution, it dynamically requests one or more cell indexes from the heap manager. The heap manager uses the data structure to find one or more contiguous open cells and returns a single cell index to the application. If the application requested one cell, then the heap manager returns a single index. If, on the other hand, the application requests more than one cell, then the heap manager tries to find the requested number of contiguous cell indexes to enable a contiguous block of memory to be allocated to the application. Once the heap manager finds a block of memory that is the correct size, it will return the cell index of the first cell to the application. The application will write its data to the memory starting at the starting index and the heap manager will update the cell index data structure to indicate that the associated cells have been allocated.
The data structure that is used to store the cell indexes, and keep track of free and occupied cells, represents overhead. For example, current solutions have an overhead, on average, anywhere from 8 to 28 bytes per memory allocation. Since each memory allocation results in allocation of one or more cells, if all memory allocations are a single cell, then the overhead is huge.
Since memory ranges of cells may be allocated, and then subsequently released, the memory tends to become fragmented meaning that allocated cells are interspersed with unallocated cells. For example, if an application requests and is allocated two cells, and subsequently releases the two cells, those two available cells may not be contiguous with another available cell. Hence, the two cells would not be available to be allocated in response to a request by another application for an allocation of four cells. Fragmentation thus can make memory regions effectively unavailable for use in fulfilling subsequent requests, even though technically the cells are not in use and hence should be available. Defragmentation is very difficult, since moving memory allocations involves reallocating memory locations to the applications.
A heap manager thus aims to minimize memory footprint required per cell index data structure (minimize overhead), to minimize fragmentation, and to minimize the search time to allocate or free cells. This last aim is associated with performance—it is desirable to use a heap management scheme that is able to efficiently find the next free index when a memory allocation is received so that the heap manager is not a bottleneck in memory performance.
Unfortunately, existing heap managers fall short in one or more of these categories. For example, many current solutions use extensive overhead to try to optimize placement of allocations within existing memory allocations to minimize fragmentation of the heap. Other solutions use a simple linked list keep track of open memory cells, which allows for reduced overhead but can cause extensive fragmentation. Accordingly, it would be advantageous to provide a highly efficient heap management scheme.